class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;

        m = matrix.size(), n = matrix[0].size();
        memo.resize(m, vector<int>(n, 0));
        this->matrix = matrix;

        int maxLen = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxLen = max(maxLen, dfs(i, j));
            }
        }
        return maxLen;
    }

private:
    int m, n;
    vector<vector<int>> memo;
    vector<vector<int>> matrix;
    const vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

    int dfs(int i, int j) {
        if (memo[i][j] != 0) return memo[i][j];

        int maxPath = 1;

        for (auto& [dx, dy] : dirs) {
            int ni = i + dx, nj = j + dy;
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
                maxPath = max(maxPath, 1 + dfs(ni, nj));
            }
        }

        return memo[i][j] = maxPath;
    }
};